package exec;

import java.nio.file.attribute.FileTime;
import java.util.*;

/**
 * @Description 数组中和为 0 的三个数
 * @Date 2022/11/8 16:58
 * @Created by wangjun
 */
public class ThreeSum {


    /**
     * 功能描述: 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
     * <p>
     * 你返回所有和为 0 且不重复的三元组。
     * <p>
     * 注意：答案中不可以包含重复的三元组。
     *
     * @Param: [nums]
     * @Return: java.util.List<java.util.List < java.lang.Integer>>
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            int firstNum = nums[i];
            int towNum = nums[i + 1];
            for (int j = i + 2; j < nums.length; j++) {
                int threeNum = nums[j];
                if (firstNum + towNum + threeNum == 0) {
                    result.add(Arrays.asList(nums[i], nums[i + 1], nums[j]));
                }
            }
        }
        return result;
    }

    public static List<List<Integer>> threeSum1(int[] nums) {
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> asList = Arrays.asList(nums[i], nums[j], nums[k]);
                        System.out.println(Arrays.toString(asList.toArray()));
                        for (List<Integer> l : result) {
                            if (!l.containsAll(asList)) {
                                result.add(asList);
                            }
                        }
                    }
                }
            }
        }
        return result;
    }

    /**
     * 功能描述: 找出和为0的三个数，采用循环加双指针
     *
     * @Param: nums 给定的数组
     * @Return: java.util.List<java.util.List < java.lang.Integer>>
     */
    public static List<List<Integer>> threeSum2(int[] nums) {
        int n = nums.length;
        // 先针对数组进行排序
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int firstIndex = 0; firstIndex < n - 1; firstIndex++) {
            // 需要和上一次枚举的数不相同
            if (firstIndex > 0 && nums[firstIndex] == nums[firstIndex - 1]) {
                continue;
            }
            int threeIndex = n - 1;
            // 转换target
            int target = -nums[firstIndex];
            for (int secondIndex = firstIndex + 1; secondIndex < n - 1; secondIndex++) {
                // 需要和上一次枚举的数不相同
                if (secondIndex > firstIndex + 1 && nums[secondIndex] == nums[secondIndex - 1]) {
                    continue;
                }
                // 改变最右侧指针
                while ((secondIndex < threeIndex) && target < nums[secondIndex] + nums[threeIndex]) {
                    threeIndex--;
                }
                if (secondIndex == threeIndex) {
                    break;
                }
                if (target == nums[secondIndex] + nums[threeIndex]) {
                    result.add(Arrays.asList(nums[firstIndex], nums[secondIndex], nums[threeIndex]));
                }
            }
        }
        return result;
    }

    public static List<Integer> sumIsTarget(int[] array, int target) {
        if (array.length == 0) {
            return null;
        }
        List<Integer> result = new ArrayList<>();
        int n = array.length;
        // 数组排序，升序
        Arrays.sort(array);
        for (int first = 0; first < n - 1; first++) {
            int three = n - 1;
            int div = target - array[first];
            for (int tow = first + 1; tow < n - 1; tow++) {
                while (tow < three && div < array[tow] + array[three]) {
                    three--;
                }
                if (div == array[tow] + array[three]) {
                    result.add(array[first]);
                    result.add(array[tow]);
                    result.add(array[three]);
                    System.out.println(Arrays.toString(result.toArray()));
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] ints = {-1, 5, 1, 2, -1, -4}; // target = 8
//        int[] ints = {0, 1, 1};
//        List<List<Integer>> lists = sumIsTarget(ints);
        List<Integer> lists = threeSum3(ints, 0);
        System.out.println(Arrays.toString(lists.toArray()));
    }

    public static List<Integer> threeSum3(int[] array, int target) {
        if (array.length == 0) {
            return null;
        }
        Arrays.sort(array);
        List<Integer> result = new ArrayList<>(3);
        for (int i = 0; i < array.length; i++) {
            int difference = target - array[i];
            int low = i + 1, high = array.length - 1;
            while (low <= high) {
                if (difference == array[low] + array[high]) {
                    result.add(array[i]);
                    result.add(array[low]);
                    result.add(array[high]);
                    return result;
                }
                if (difference < array[low] + array[high]) {
                    high--;
                } else {
                    low++;
                }
            }
        }
        return null;
    }
}
